#coding: utf-8

from itertools import chain
from squareunit import BUnit, DUnit, VUnit, HUnit


class BoardFactory(type):

    def __init__(cls, name, bases, dic):
        super(BoardFactory, cls).__init__(name, bases, dic)
        cls.instances = {}

    def __call__(cls, bu, du, vu, hu):
        mask = 0
        for unit in [bu, du, vu, hu]:
            if mask & unit.mask:
                return
            mask |= unit.mask
        assert bu.count + du.count + vu.count + hu.count == 18
        hash = bu.hash | du.hash | vu.hash | hu.hash
        if hash not in cls.instances:
            instance = super(BoardFactory, cls).__call__(bu, du, vu, hu, hash, mask)
            cls.instances[hash] = instance
        return cls.instances[hash]


class Board(object):
    __metaclass__ = BoardFactory

    def __init__(self, bu, du, vu, hu, hash, mask):
        self.bu = bu
        self.du = du
        self.vu = vu
        self.hu = hu
        self.hash = hash
        self.mask = mask

    def __hash__(self):
        return self.hash

    @property
    def nexts(self):
        bu, du, vu, hu = self.bu, self.du, self.vu, self.hu
        mask = self.mask
        for nbu in bu.nexts(mask):
            board = Board(nbu, du, vu, hu)
            yield board
        for nds in du.nexts(mask):
            board = Board(bu, nds, vu, hu)
            yield board
        for nvs in vu.nexts(mask):
            board = Board(bu, du, nvs, hu)
            yield board
        for nhs in hu.nexts(mask):
            board = Board(bu, du, vu, nhs)
            yield board

    def __str__(self):
        seq = [[' ', ' ', ' ', ' '],
               [' ', ' ', ' ', ' '],
               [' ', ' ', ' ', ' '],
               [' ', ' ', ' ', ' '],
               [' ', ' ', ' ', ' ']]
        for square in chain(self.bu.squares, self.du.squares, self.hu.squares, self.vu.squares):
            for x, y in square.positions:
                seq[y][x] = square.C
        return '\n'.join(''.join(i) for i in seq)

    def __repr__(self):
        return ''.join(str(self).split('\n'))


def solve(board):
    board.parent = None
    node = 0
    bmap = {board: 0}
    dmap = {0: [board]}
    depth = 0
    while dmap[depth]:
        boards = dmap[depth]
        depth += 1
        dmap[depth] = []
        for board in boards:
            for new in board.nexts:
                if new not in bmap:
                    node = node + 1
                    if new.bu.squares[0].position == 13:
                        result = [board, new]
                        while board.parent is not None:
                            board = board.parent
                            result.insert(0, board)
                        return result, node
                    new.parent = board
                    dmap[depth].append(new)
                    bmap[new] = depth


def main():
    board = Board(BUnit([(1, 0)]),
        DUnit([(0, 0), (3, 0), (0, 3), (3, 3)]),
        VUnit([(0, 1), (3, 1)]),
        HUnit([(1, 2), (1, 3), (1, 4)]))
    return solve(board)

if __name__ == "__main__":
    import time
    start = time.time()
    boards, node = main()
    for i, board in enumerate(boards):
        print '%d.......' % i
        print board
    print 'node count: %d' % node
    print 'use time:', time.time() - start
